package q1022_sumRootToLeaf;

import CommonClass.Common.TreeNode;

import java.util.Stack;

public class Solution_3 {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(1);
        node.left.left = new TreeNode(1);

        System.out.println(new Solution_3().sumRootToLeaf(node));
    }
    public int sumRootToLeaf(TreeNode root) {
        int ans = 0, sum = 0;// 答案、当前栈顶节点表示的值
        Stack<TreeNode> stack=new Stack<>();
        TreeNode pre = null;// 记录上一刚刚轮遍历过的节点，只记录含“右节点”的部分
        while (root != null || !stack.isEmpty()) {
            // 对于while里面条件解释：1、栈内没有节点了，那么无需继续；2、root == null，说明最后遍历过的那一支已经遍历完成了
            // 首先，规则是，对于一个节点，需要先遍历左支，再遍历右支
            while (root != null) {
                sum = sum << 1 | root.val;
                stack.push(root);
                root = root.left;
            }
            // 这一支的无限左支已经到尽头（本循环最开始root的左支节点全部入栈），需要进行操作来统计数据：
            root = stack.peek();// 此时这个节点对应的是sum，不要着急pop呀，就这里出岔子好久
            // root要么是叶节点，要么它的右支有可能没有遍历过（因为上边的规则是先遍历左支呀）
            if (root.left == root.right) {
                // root是叶节点，此时需要加上，并且sum需要去掉一位
                ans += sum;
                sum /= 2;
                pre = stack.pop();
                root = null;// 为了标记这一支以及下面已经遍历完成表示左右都不用向下了
            }       else if (root.right == null || root.right == pre) {
                // 此时右节点为空或者右节点已经被遍历过，则需要返回上一层：
                pre = stack.pop();
                sum /= 2;
                root = null;// 为了标记这一支以及下面已经遍历完成表示左右都不用向下了
            } else {
                // 此时右支没有遍历，那么就先把此时的第一个右节点拿进来
                root = root.right;
                // 这样就遍历到某个“右支”的起始位置了，下次循环需要重复上述ook操作
            }
        }
        return ans;
    }

}
